#pragma once
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

const int byte_const = 32;
#define WHITE 0
#define GREY 1
#define BLACK 2

class IGraph
{	
public:
	virtual ~IGraph() { };
	virtual int get_number_of_vertice() const = 0;
	virtual vector<int> get_list_adjacents(int vertex) const = 0;
	virtual size_t byte_size() const = 0;
};

class Graph_Matrix : public IGraph
{
private:
	vector<vector<char> >graph_matrix;

public: 
	explicit Graph_Matrix(int size, const vector<pair<int, int> >& edge);
	int get_number_of_vertice() const;
	vector<int> get_list_adjacents(int vertex) const;
	size_t byte_size() const;

};

Graph_Matrix :: Graph_Matrix(int size, const vector<pair<int, int> >& edge)
{
	int graph_size = size;
	graph_matrix.assign(graph_size, vector<char>(graph_size, 0));
	
	for(int cur_edge = 0; cur_edge < edge.size(); ++cur_edge)
	{
		int start_vertex = edge[cur_edge].first;
		int final_vertex = edge[cur_edge].second;
		graph_matrix[start_vertex][final_vertex] = 1;
	}
}

int Graph_Matrix :: get_number_of_vertice() const
{
	return graph_matrix.size();
}

vector<int> Graph_Matrix :: get_list_adjacents(int key_vertex) const
{
	vector<int>list;

	for(int incident_vertex = 0; incident_vertex < graph_matrix.size(); ++incident_vertex)
	{
		if (graph_matrix[key_vertex][incident_vertex] == 1)
			list.push_back(incident_vertex);
	}

	return list;
}

size_t Graph_Matrix :: byte_size() const 
{
	return ((graph_matrix.size() * graph_matrix.size())/byte_const) * sizeof(int);
}

class Graph_List : public IGraph
{
private:
	vector<vector<int> >graph_list;
	int graph_size;
	int edges_size;
public: 
	explicit Graph_List(int graph_size, vector<pair<int, int> > & edge);
	int get_number_of_vertice() const;
	vector<int> get_list_adjacents(int vertex) const;
	size_t byte_size() const;

};

Graph_List :: Graph_List(int size, vector<pair<int, int> > & edge)
{
	edges_size = edge.size();
	graph_size = size;
	graph_list.resize(graph_size);

	for(int current_edge = 0; current_edge < edge.size(); ++current_edge)
	{
		int start_vertex = edge[current_edge].first;
		int final_vertex = edge[current_edge].second;
		graph_list[start_vertex].push_back(final_vertex);
	}
}

int Graph_List :: get_number_of_vertice() const
{
	return graph_size;
}

vector<int> Graph_List :: get_list_adjacents(int vertex) const
{
	vector<int>list = graph_list[vertex];

	return list;
}

size_t Graph_List :: byte_size() const 
{
	return (graph_size + edges_size) * sizeof(int);
}

unique_ptr<IGraph> compact_graph(int size, vector<pair<int, int> >& edge)
{
	if ((size * size)/byte_const < size + edge.size())
	{
		unique_ptr<IGraph> matrix_representation (new Graph_Matrix(size, edge));
		return move (matrix_representation);
	}
	else
	{
	unique_ptr<IGraph> list_representation (new Graph_List(size, edge));
	return move (list_representation);
	}	
}

class topological_sorting
{
public:
	int FIRST_TYPE_OPERATION ;
	vector<int>index;

	void initialize(const unique_ptr<IGraph> & graph, int start)
	{
		
	}

	void enter_vertex (const unique_ptr<IGraph> & graph, int vertex, vector<int> & color)
	{
		
	}

	void before_edge(const unique_ptr<IGraph> & graph, int vertex, int to, vector<int> & color)
	{
		
	}

	void after_edge (const unique_ptr<IGraph> & graph, int vertex, int to, vector<int> & color)
	{
		
	}

	void exit_vertex (const unique_ptr<IGraph> & graph, int vertex, vector<int> & color)
	{
		index.push_back(vertex);
	}
		
	void final(const unique_ptr<IGraph> & graph)
	{
	vector<int> top_sort(index.size());
	for(int i = 0; i<index.size(); ++i)top_sort[index[i]] = i;
	index = top_sort;
	
	}
};

template <class functor>
class commondfs
{
public:
	vector <int> color;

	commondfs(const unique_ptr<IGraph> & graph, int start, functor &f)
	{
		color.assign(graph->get_number_of_vertice(), WHITE);
		if (start >= 0 && start < graph->get_number_of_vertice())color[start] = GREY;
		f.initialize(graph, start);
	}
	
	void dfscycle(const unique_ptr<IGraph> & graph, functor &f)
	{
		for(int start = 0; start < graph->get_number_of_vertice(); ++start)
			if (color[start] == WHITE) 
				dfs(graph, start, f);
		f.final(graph);
	}

	void dfs(const unique_ptr<IGraph> & graph, int vertex, functor &f)
	{
		f.enter_vertex(graph,vertex, color);
		color[vertex] = GREY;
		vector<int> adjacents = graph->get_list_adjacents(vertex);

		for(int i = 0; i<adjacents.size(); ++i)
		{
			int to = adjacents[i];
			f.before_edge(graph, vertex, to, color);
			if (color[to] == WHITE)
				dfs(graph, to, f);
			f.after_edge(graph, vertex, to, color);
		}
		
		color[vertex] = BLACK;
		f.exit_vertex(graph, vertex, color);
	}

	
};

vector<int>top_sort(const unique_ptr<IGraph> & graph)
{
	topological_sorting Top_Sort;
	commondfs<topological_sorting> sorted(graph, -1, Top_Sort);
	sorted.dfscycle(graph, Top_Sort);
	return Top_Sort.index;
}

vector<int> BFS (const unique_ptr<IGraph> & graph, int vertex){
	vector<int> min_distance;
	int INF = 1000000;
	min_distance.assign(graph->get_number_of_vertice(), INF);
	queue<int>queue_of_vertice;
	vector<bool> used(graph->get_number_of_vertice(), false);
	queue_of_vertice.push(vertex);
	while(!queue_of_vertice.empty())
	{
		int new_vertex = queue_of_vertice.front();
		used[new_vertex] = true;
		queue_of_vertice.pop();
		vector<int>adjacents_to_vertex = graph->get_list_adjacents(new_vertex);
		for(int current_vertex = 0; current_vertex < adjacents_to_vertex.size(); ++current_vertex)
		{
			if (!used[adjacents_to_vertex[current_vertex]])
			{
				min_distance[adjacents_to_vertex[current_vertex]] = min(min_distance[adjacents_to_vertex[current_vertex]], min_distance[new_vertex] + 1);
				queue_of_vertice.push(adjacents_to_vertex[current_vertex]);
			}
		}
	}
	return min_distance;
}
